ST_Split fails to split on existing vertex

[strk]

This bug was found in #2172 as it affects topology building. In that case a line (899.112421269008 units long) gets splitted by one if its vertices which is around halfway into it:

select st_line_locate_point(geom, st_pointn(geom, 745)) 
 from offending;
    0.692338478022024

The return from ST_Split, unioned back togheter, does NOT give the original geometry back.

This is most likely due to the fact that the split is not occurring exactly where the original vertex is but rather on a close-by point which results in snapping a segment on the new point.

[strk]

Reduced input:

Geom: 01020000003000000034030F8FB15866C0F2311FFD3B9A53C0571C87CF1BB65BC0182DB847DB9052C0DD02290D6FD559C02F7EA87CBE4052C0EBD57BDEEBF658C05CA18B9FA81B52C03C751F17F49C58C082295A18F81352C02AC660DBE29758C0BD3F7138891352C024E660D7C36758C0193E2B506C0F52C01D4D6BE4DC6358C0186CD2EE160F52C0B0A82B72712658C0D615710CD70952C03E87530FC79F52C07801A9AEED9051C074384E71C20552C05AD308B7C38351C085B97825D38351C03EECD30CE44551C00AF3A6FB11BF50C00320F6BB32E850C097C9520EFA244DC03863E28251BE4FC0A4B3920AA7914CC0ACD200FB29784FC0639ED4794B9B3E40D0FA429CF64751C0278B78728C053F4062D63900D64951C0A278AC84F4763F40695EA7A9D54B51C05124D2D9CEA53F40AB7A130DA94C51C0E3109B452D8740402ACA27BE035351C0F8892AEE70E14040C0C8143E325651C0A68ED2B8137541400C3621B5034951C0122CECA8182A4340475AFAB1FE2151C029EB5954687C44408AC357F6F41F51C0E55DF900B0DA444010DD0F91631F51C0DFA81899F1475140C361D3C93F0A51C01DBF07C3577751406CEDA34C290951C0234604DC104E5440EF10F2807BF850C08FEE52B6CAE15F4002BF1C6676B450C0D11859C78B31604033AF14B57EB150C0534A4AD17C516140BD35742847A450C0051A57A65BB061405B9E445AEC9F50C025BD3794D1186240576B3AEAE4C150C07676E581713A6240EA15C43DD4CC50C0FB6727D8B227634081328438FC1951C0914206184C4C634097799421E32551C05FA9537DA09A634098A9473C5C3F51C0F81C41640DA26340C5773D6AC64151C05AF3E1D5815665405E3A4A2BB6CF51C0591DE7ECD21F66400D33BFE91C7E53C0000000C0392E6640000000600E8153C0000000C00D50664000000060038A53C0000000A0317E664000000000F89253C0000000E0FF7F6640000000C04E9353C0000000000080664000000000008056C000000000008066C000000000008056C000000000008066C0000000E04D9353C034030F8FB15866C0F2311FFD3B9A53C0
Split point: 46

[strk]

Further reduction:

Geom: 01020000001000000034030F8FB15866C0F2311FFD3B9A53C0571C87CF1BB65BC0182DB847DB9052C0EBD57BDEEBF658C05CA18B9FA81B52C074384E71C20552C05AD308B7C38351C0A4B3920AA7914CC0ACD200FB29784FC0F8892AEE70E14040C0C8143E325651C0234604DC104E5440EF10F2807BF850C08FEE52B6CAE15F4002BF1C6676B450C0051A57A65BB061405B9E445AEC9F50C05AF3E1D5815665405E3A4A2BB6CF51C0591DE7ECD21F66400D33BFE91C7E53C0000000E0FF7F6640000000C04E9353C0000000000080664000000000008056C000000000008066C000000000008056C000000000008066C0000000E04D9353C034030F8FB15866C0F2311FFD3B9A53C0
Split point: 14

Or in a self-contained test:

with inp as ( 
 SELECT 
'01020000001000000034030F8FB15866C0F2311FFD3B9A53C0571C87CF1BB65BC0182DB847DB9052C0EBD57BDEEBF658C05CA18B9FA81B52C074384E71C20552C05AD308B7C38351C0A4B3920AA7914CC0ACD200FB29784FC0F8892AEE70E14040C0C8143E325651C0234604DC104E5440EF10F2807BF850C08FEE52B6CAE15F4002BF1C6676B450C0051A57A65BB061405B9E445AEC9F50C05AF3E1D5815665405E3A4A2BB6CF51C0591DE7ECD21F66400D33BFE91C7E53C0000000E0FF7F6640000000C04E9353C0000000000080664000000000008056C000000000008066C000000000008056C000000000008066C0000000E04D9353C034030F8FB15866C0F2311FFD3B9A53C0'
  ::geometry as g, 
  14 as p 
) 
select st_equals(
  g,
  st_union(
    st_geometryn(st_split(g, st_pointn(g,p)), 1), 
    st_geometryn(st_split(g, st_pointn(g,p)), 2)
  )
) from inp;

[strk]

NOTE: the self-contained test above should return TRUE, and does return TRUE on a 64bit linux, but returns FALSE on a 32bit linux.

[strk]

NOTE: location of the vertex on the line is near the end. Line_Locate_Point returns 0.9827344+ for it.

[strk]

I think the solution here would be to make available (at least at the liblwgeom level) a more robust line location computer that reports distance on a local segment rather than on the whole line. This would be a pair composed by vertex index _and_ distance from the vertex. Any exact vertex would have a distance of 0, for full robustness of those cases.

[strk]

Another solution (short term) is to augment the "vertex snap tolerance" used in the lwline_split_by_point_to function. Currently it uses a tolerance of 1e-14, setting to 1e-13 fixes this case. We could compute a tolerance based on input line length (longer line, higher tolerance).

[strk]

Fixed by basing the tolerance on line length with r10972 in 2.0 branch and r10973 in trunk